import java.util.*;

public class class03 {
    public class TreeNode{
        char val;
        TreeNode left;
        TreeNode right;
        public TreeNode(char val){
            this.val = val;
        }
    }

//    public static int i = 0;
//    层序遍历
    public static  List<LinkedList<Character>> levelOrder(TreeNode root){
        List<LinkedList<Character>> retList = new ArrayList<>();
        if (root == null){
            return retList;
        }
//        队列
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        while(!queue.isEmpty()){
            int size = queue.size();
            List<Character> list = new ArrayList<>();
            while(size!=0){
                TreeNode cur = queue.poll();
                list.add(cur.val);
                size--;
                if (cur.left != null){
                    queue.offer(cur.left);
                }
                if (cur.right != null){
                    queue.offer(cur.right);
                }
            }
            retList.add((LinkedList<Character>) list);
        }
        return retList;
//        TreeNode cur = root;
//        i = queue.size();
//        if (!queue.isEmpty()){
//            while (i != 0){
//                queue.poll();
//                if (){
//
//                }
//                i--;
//            }
        }

//        判断一棵树是不是完全二叉树
    public boolean isCompleteTree(TreeNode root){
        if (root==null){
            return true;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        while(!queue.isEmpty()){
            TreeNode cur = queue.poll();
            if (cur != null){
                queue.offer(cur.left);
                queue.offer(cur.right);
            }else{
                break;
//                结束后遍历队列所有元素
            }
        }
        while(!queue.isEmpty()){
            TreeNode cur = queue.poll();
            if (cur != null){
                return false;
            }
        }
        return true;
    }

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root==null){
            return root;
        }
        if(root==p || root==q){
            return root;
        }
        // 在左树当中查找p或者q
        TreeNode left = lowestCommonAncestor(root.left,p,q);
        TreeNode right = lowestCommonAncestor(root.right,p,q);
        if(left!=null && right!=null){
            return root;
        }else if(left!=null){
            return left;
        }else{
            return right;
        }
    }

    public TreeNode lowestCommonAncestor2(TreeNode root, TreeNode p, TreeNode q){
        if (root==null){
            return null;
        }
        Stack<TreeNode> s1 = new Stack<>();
        Stack<TreeNode> s2 = new Stack<>();
//        先得到p的路径
//        再求q的路径
        getPath(root,p,s1);
        getPath(root,q,s2);
//        让两个栈的长度相等
        int size1 = s1.size();
        int size2 = s2.size();
        if (size1>size2){
            int size = size1-size2;
            while(size != 0){
                s1.pop();
                size--;
            }
        } else  {
            int size = size2-size1;
            while(size != 0){
                s2.pop();
                size--;
            }
        }
//        再一起弹出元素，若遇到相同的，则是公共祖先
        while(!s1.isEmpty() && !s2.isEmpty()){
//            s1.peek()==s2.peek();   比较的是两个对象的内容是否相同
//            s1.peek().equals(s2.peek())  比较的是两个对象的引用是否相同
            if (s1.peek().equals(s2.peek())){
                return s1.pop();
            }else {
                s1.pop();
                s2.pop();
            }
        }
//        如果栈为空，则没有
        return null;
    }
    private boolean getPath(TreeNode root,TreeNode node,Stack<TreeNode> stack){
        if (root==null){
            return false;
        }
        stack.push(root);
        if (root==node){
            return true;
        }
        boolean flgLeft = getPath(root.left,node,stack);
        if (flgLeft){
            return true;
        }
        boolean flgRight = getPath(root.right, node, stack);
        if (flgRight){
            return true;
        }
        stack.pop();
        return false;
    }

//    二叉树的前序遍历
    public String tree2Str(TreeNode root){
        StringBuilder stringBuilder = new StringBuilder();
        tree2strChild(root,stringBuilder);
        return stringBuilder.toString();
//        System.out.println("(");
//        if (root==null){
//            return null;
//        }
    }

    public void tree2strChild(TreeNode root,StringBuilder stringBuilder){
        if (root==null){
            return;
        }
        stringBuilder.append(root.val);
//        递归左树
        if (root.left != null){
            stringBuilder.append("(");
            tree2strChild(root.left,stringBuilder);
//            走到这，代表一棵树走完了
            stringBuilder.append(")");
        }else {
            if (root.right == null){
                return;
            }else {
                stringBuilder.append("()");
            }
        }
//        递归右数
        if (root.right != null){
            stringBuilder.append("(");
            tree2strChild(root.right,stringBuilder);
            System.out.println(")");
        }else {
//            右数为空什么都不做
            return;
        }
    }

//    二叉树前序遍历非递归
//    申请栈
    public List<Character> preorderTraversal(TreeNode root) {
        List<Character> list = new ArrayList<>();
        if (root==null){
//            return null;  有返回值，千万不要这样，可能会报错
            return list;
        }
        TreeNode cur = root;
        Stack<TreeNode> stack = new Stack<>();
//         cur会一直往左边走
        while (cur != null && !stack.isEmpty()){
            while(cur != null){
                stack.push(cur);
                list.add(cur.val);
                cur = cur.left;
            }
            TreeNode top = stack.pop();
            cur = top.right;
        }
       return list;
//        TreeNode top = stack.pop();
//        cur = top.right;
//
//        stack.push(root.val);
//        while(!stack.isEmpty()){
////            打印并入栈
//            System.out.println(root.val);
//            stack.push(root.left.val);
////            左树入栈
//            char top = stack.peek();
//        }
        }

//        非递归的中序遍历
    public List<Character> inorderTraversal(TreeNode root) {
        List<Character> list = new ArrayList<>();
        if (root==null){
            return list;
        }
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        while(root != null ){
            while(root != null){
                stack.push(cur);
                cur = cur.left;
            }
            TreeNode top = stack.pop();
            list.add(top.val);
            cur = top.right;

        }
        return list;
    }

//    非递归的后续遍历
    public List<Character> postorderTraversal(TreeNode root) {
        List<Character> list = new ArrayList<>();
        if (root == null){
        return list;
        }
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        TreeNode prev = root;
        while(root != null || !stack.isEmpty()){
            while(root != null){
                stack.push(cur);
                cur = cur.left;
            }
            TreeNode top = stack.peek();
            if (top.right == null || top.right == prev){
//              最后一棵左树，可以弹出栈，进入list了
                stack.pop();
                list.add(top.val);
//                prev指向top
                prev = top;
            }else {
                cur = top.right;
            }
        }

        return list;
    }
}

